#define _CRT_SECURE_NO_WARNINGS 1
#include"dsoj.h"
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
{
    struct ListNode* cur1 = list1;
    struct ListNode* cur2 = list2;
    struct ListNode* new = NULL;
    struct ListNode* newhead = NULL;
    while (cur1 && cur2)
    {
        if (cur1->val <= cur2->val)
        {
            if (newhead == NULL)
            {
                newhead = cur1;
                new = cur1;
            }
            else {
                new->next = cur1;
                new = new->next;
            }
            cur1 = cur1->next;
        }
        else {
            if (newhead == NULL)
            {
                newhead = cur2;
                new = cur2;
            }
            else {
                new->next = cur2;
                new = new->next;
            }
            cur2 = cur2->next;
        }
    }
    if (cur1 == 0)
    {
        while (cur2)
        {
            new->next = cur2;
            cur2 = cur2->next;
        }

    }
    else
    {
        while (cur1)
        {
            new->next = cur1;
            cur1 = cur1->next;
        }

    }
    return newhead;
}



void CLPrint(struct ListNode* phead)
{
    struct ListNode* cur = phead;
    while (cur)
    {
        printf("%d->", cur->val);
        cur = cur->next;
    }
    printf("NULL\n");
}
bool hasCycle(struct ListNode* head) {
    if (head == 0 || head->next == 0)
        return 0;
    struct ListNode* slow = head;
    struct ListNode* fast = head->next;
    while (slow != fast && fast != 0 && fast->next != 0)
    {
        fast = fast->next->next;
        slow = slow->next;
    }
    if (slow == fast)
        return 1;
    return 0;
}
struct ListNode* copyRandomList(struct ListNode* head) {
    struct ListNode* cur = head;
    while (cur)
    {
        struct ListNode* copy = (struct ListNode*)malloc(sizeof(struct ListNode));
        copy->val = cur->val;
        struct ListNode* next = cur->next;
        cur->next = copy;
        copy->next = next;
        cur = next;
    }
    cur = head;
    while (cur)
    {
        struct ListNode* copy = cur->next;
        if (cur->random == NULL)
        {
            copy->random = NULL;
        }
        else
        {
            copy->random = cur->random->next;
        }
        cur = copy->next;
    }
    struct ListNode* newhead = head->next;
    cur = head;
    while (cur->next->next)
    {
        struct ListNode* copy = cur->next;
        struct ListNode* next = copy->next;
        copy->next = next->next;
        cur->next = next;
        cur = next;
    }
    cur->next = NULL;
    return newhead;
}